package hash;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description: 实现一个简单的哈希桶
 * User:周次煜
 * Date: 2024-04-22
 * Time：10:16
 */
public class HashBucket {


    // 存放链表数组
    Node []array;

    // 实际元素个数
    int useSize;


    private static final int DEFAULTSIZE=10;


    // 定义一个内部类为节点
    static class Node {
       int val;
       Node next;

       int key;
       public Node(int key,int val) {
           this.key=key;
           this.val = val;
       }
   }



   public HashBucket() {
       array=new Node[DEFAULTSIZE];

   }

    /**
     * 插入方法
     * @param val 需要插入的数据
     */
    void put(int key,int val) {

        // 判断是否满
        if (isFull()) {
        insertFunc2(key,val);
        return;
        }

        insertFunc1(key,val);

   }

    /**
     * 未满时普通插入
     * @param val 需要插入的数据
     */

   private void insertFunc1(int key,int val) {
       int sz=array.length;
       int index= key % sz;

       // 如果出现 key 重复 就修改 val 值
       Node cur=array[index];
       while (cur != null) {
           if (cur.key == key) {
               cur.val=val;
               return;
           }
           cur=cur.next;
       }

       Node node=new Node(key,val);

       node.next=array[index];
       array[index]=node;
       useSize++;
   }

    /**
     * 扩容方法
     * @param val 插入数据
     * 先扩容一个新数组
     * 然后把旧数组整合放入新数组
     * 最后旧数组成为新数组
     */

    private void insertFunc2(int key ,int val) {
       Node cur=null;

       Node[] newArray= new Node[2 * array.length];

       int newLength = 2 * array.length;

       for (int i = 0; i < array.length; i++) {

           cur=array[i];
           while (cur != null) {
              int m = cur.key;

              // 先让 node 记住 cur 的下个节点
              Node node = cur.next;
              int index = m % newLength;

              cur.next = newArray[index];
              newArray[index] = cur;

                cur=node;
          }

       }

       Node til=new Node(key,val);

       int index=key%newLength;

        // 如果出现 key 重复 就修改 val 值
        Node curN=array[index];
        while (curN != null) {
            if (curN.key == key) {
                curN.val=val;
                return;
            }
            curN=curN.next;
        }

       til.next=newArray[index];

       newArray[index]=til;

       useSize++;

       array=newArray;
   }

    /**
     * 查找该节点
     * @param key 需要查找的数据
     * @return 返回该数据的节点
     */
  public int get(int key) {
      if (isEmpty()) return -1;
        int index=key%array.length;
        Node cur=array[index];
        while (cur != null) {
            if (cur.key==key) {
                return cur.val;
            }
            cur=cur.next;
        }

        return -1;
   }

    /**
     * 查找是否该节点
     * @param key 需要查找的数据
     * @return 返回是否找到
     */

  public   boolean contains(int key) {
      if (isEmpty()) return false;

        int index=key % array.length;
        Node cur=array[index];

        while (cur != null) {
            if (cur.val==key) {
                return true;
            }
            cur=cur.next;
        }

        return false;
    }



    public boolean remove(int key) {
        if (isEmpty()) return false;

        int index = key % array.length;

        Node cur = array[index];

        Node node = cur;

        if (cur.key==key) {

            array[index]=cur.next;
            return true;
        }
        while (cur != null) {
            if (cur.key == key) {
                node.next = cur.next;
                useSize--;
                return true;
            }
            node = cur;
            cur = cur.next;
        }

        return false;
    }

    /**
     * 判断是否满
     * @return 返回结果
     */
    private boolean isFull() {
       return (useSize*1.0/array.length) >= 0.75;
   }

    /**
     * 判断是否为空
     * @return 返回结果
     */


   private boolean isEmpty() {
        return useSize==0;
   }



}
